package com.rui.study.algorithm.P_逆序度计算_分治思想;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2018-12-20 15:41
 **/
public class Solution {

    private int num = 0;

    public int solution(int[] a) {
        if (a == null || a.length <= 1) return 0;
        recursive(a, 0, a.length - 1);
        return num;
    }

    public void recursive(int[] a, int p, int q) {
        if (p >= q) return;
        int m = (p +q) / 2;
        recursive(a, p, m);
        recursive(a, m + 1, q);
        merge(a, p, m, q);
    }

    public void merge(int[] a, int p, int m, int q) {
        int[] temp = new int[q - p + 1];
        int i = p, j = m + 1, k = 0;
        while (i <= m && j <= q) {
            if (a[i] < a[j]) {
                num += j - m - 1;   // 理解：我进入temp的时候，对面（比我小的）已经溜了下去的个数j-m-1就是我的逆序对。// 非常巧妙！！！
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }

        while (i <= m) {            // 理解：对面（比我小的）都溜完了，孤独如我进入temp的时候，对面的个数j-m-1就是我的逆序对
            num += j - m - 1;
            temp[k++] = a[i++];
        }

        while (j <= q) {
            temp[k++] = a[j++];
        }

        for (i = 0; i <= q - p; i++) {
            a[p + i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] a = {1,3,4,2};
        System.out.println(new Solution().solution(a));
    }
}
